package Preferred_algorithm.Topic6_Simulation_Algorithm;

import java.util.HashMap;
import java.util.Map;

public class Topic6_Simulation_Algorithm {
    //1576.替换所有的问号
    //https://leetcode.cn/problems/replace-all-s-to-avoid-consecutive-repeating-characters/description/

    public String modifyString(String ss) {
        char[] s = ss.toCharArray();
        int n = s.length;
        for(int i = 0 ; i < n ; i++){
            if(s[i]=='?'){
                for(char ch = 'a'; ch <= 'z';ch++){
                    if((i==0||s[i-1]!=ch)&&(i==n-1||s[i+1]!=ch)){
                        s[i]=ch;
                        break;
                    }
                }
            }
        }
        return String.valueOf(s);
    }

    //495.提莫攻击
    //https://leetcode.cn/problems/teemo-attacking/description/

    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int ret = 0;
        for (int i = 0; i < timeSeries.length - 1; i++) {
            int x = timeSeries[i + 1] - timeSeries[i];
            if (x >= duration)
                ret += duration;
            else
                ret += x;
        }
        return ret += duration;
    }

    //Z 字形变换
    //https://leetcode.cn/problems/zigzag-conversion/

    public String convert(String ss, int numRows) {
        char[] s = ss.toCharArray();
        if (numRows == 1)
            return ss;
        int n = ss.length(), d = numRows*2-2;
        char[] ret = new char[n];
        int count = 0;

        // 第一行
        for (int i = 0; i < n; i += d) {
            ret[count++] = s[i];
        }

        // 中间行
        for (int k = 1; k < numRows - 1; k++) { //枚举行

            for (int i = k, j = d - k; i < n || j < n; i += d, j += d) {  //枚举列

                //i ，j += d 还要再判断一次，否则会越界
                if (i < n)
                    ret[count++] = s[i];
                if (j < n)
                    ret[count++] = s[j]; //不要忘记 count++
            }
        }

        // 最后一行
        for (int i = numRows - 1; i < n; i += d) { //注意:最后一行的首元素为 numRows - 1
            ret[count++] = s[i];
            //不要忘记 count++
        }
        return String.valueOf(ret);
    }

    //38.外观数列
    //https://leetcode.cn/problems/count-and-say/

    public String countAndSay(int n) {
        if(n==1)return "1";
        String ret = "1";

        for(int i = 1 ; i < n ; i++){
            StringBuilder tmp = new StringBuilder();
            int len = ret.length();
            for(int left = 0 , right = 0 ; right<len ; ){
                while(right<len && ret.charAt(left)==ret.charAt(right))right++;
                tmp.append(Integer.toString(right-left));
                tmp.append(ret.charAt(left));
                left=right;
            }
            ret = tmp.toString();
        }
        return ret;
    }

    //1419.数青蛙
    //https://leetcode.cn/problems/minimum-number-of-frogs-croaking/

    public int minNumberOfFrogs(String croakOfFrogs) {
        char[] c = croakOfFrogs.toCharArray();
        String t = "croak";

        int n = t.length();

        int[] hash = new int[n];
        Map<Character, Integer> index = new HashMap<>();

        // 定义好哈希表 index
        for (int i = 0; i < n; i++) {
            index.put(t.charAt(i), i); // <字符，下标数字>
        }

        for (char ch : c) {
            if (ch != t.charAt(0)) {
                int i = index.get(ch);
                if (hash[i - 1] == 0) {
                    return -1;
                }
                hash[i]++;
                hash[i - 1]--;
            } else {
                if (hash[n - 1] != 0) {
                    hash[n - 1]--;
                }
                hash[0]++;
            }
        }

        for (int i = 0; i < n - 1; i++) {
            if (hash[i] != 0)
                return -1;
        }
        return hash[n - 1];
    }
}
